/***尚硅谷Java数据结构与java算法                  ***/
/***https://www.bilibili.com/video/BV1E4411H73v***/
/***普利姆算法           P155                   ***/
/***C++ 实现版本    written by Daniel           ***/
#include <vector>
#include <iostream>
#include <algorithm>

typedef struct eData{
    char start;
    char end;
    int weight;
    eData()=delete;
    eData(char start, char end, int weight):start(start),end(end),weight(weight){};
} eData;
//图类
class mGraph
{
public:
    mGraph()=delete;
    mGraph(int num, std::vector<char> vertexVec, std::vector<std::vector<int>> weightVec) : vertexNum(num), vertexVec(vertexVec), weightVec(weightVec)
    {
        //生成dataVec，用于给距离排序
        for(int i=0;i<vertexNum;i++){
            for (int  i = 0; j < vertexNum; j++)
            {
                if (weightVec[i][j]!=10000){
                    dataVec.push_back(eData(vertexVec[i],vertexVec[j],weightVec[i][j]));
                }
            }
            
        }
    }
    mGraph(mGraph& graph)=default;
    mGraph(mGraph&& graph)=default;
    /*
    功能：使用普利姆算法，建造一个最小生成树
    参数：start  开始的位置，即第几个节点，从零开始
    返回值： 空
    */
    void prim(int start)
    {
        //0代表没有访问过
        std::vector<bool> isVisited(vertexNum, false);
        isVisited[start] = true;
        int tempFrom = -1;
        int tempTo = -1;
        std::vector<std::pair<int, int>> path;
        //从已经访问过的节点中，找到最小距离最小的节点
        for (int k = 1; k < vertexNum; k++)
        {
            int weightMin = 10000;
            for (int i = 0; i < vertexNum; i++)
            {
                if (isVisited[i])
                {
                    for (int j = 0; j < vertexNum; j++)
                    {
                        if ((!isVisited[j]) && weightVec[i][j] < weightMin)
                        {
                            weightMin=weightVec[i][j];
                            tempFrom = i;
                            tempTo = j;
                        }
                    }
                }
            }
            path.push_back(std::make_pair(tempFrom,tempTo));
            isVisited[tempTo]=true;
        }
        int totalPath=0;
        for(const auto &item:path){
            totalPath+=weightVec[item.first][item.second];
            std::cout<<vertexVec[item.first] <<">>"<<vertexVec[item.second]<<"\t路径长度"<<weightVec[item.first][item.second]<<std::endl;
        }
        std::cout<<"路径总长度"<<totalPath<<std::endl;
    }

    void printWeight()
    {
        for(const auto& item:weightVec){
            for(const auto& item1:item){
                std::cout<<item1<<"\t";
            }
            std::cout<<std::endl;
        }
    }
private:
    int vertexNum;
    std::vector<char> vertexVec;
    std::vector<std::vector<int>> weightVec;
    std::vector<eData> dataVec;
};

//测试代码
int main()
{
    int vertexNum=7;
    std::vector<char> vertexVec({'A','B','C','D','E','F','G'});
    int arr[vertexNum][vertexNum]=
    {{10000,5,7,10000,10000,10000,2},
      {5,10000,10000,9,10000,10000,3},
      {7,10000,10000,10000,8,10000,10000},
      {10000,9,10000,10000,10000,4,10000,10000},
      {10000,10000,8,10000,10000,5,4},
      {10000,10000,10000,4,5,10000,6},
      {2,3,10000,10000,4,6,10000}};
    std::vector<std::vector<int>> weightVec(vertexNum,std::vector<int>(vertexNum,0));
    for(int i=0;i<vertexNum;i++){
        for(int j=0;j<vertexNum;j++){
            weightVec[i][j]=arr[i][j];
        }
    }
    mGraph* graph=new mGraph(vertexNum,vertexVec,weightVec);
    graph->printWeight();
    graph->prim(2);
    if (graph!=nullptr){
        delete graph;
        graph=nullptr;
    }
}